package algorithm.aStart_8number;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.TreeSet;

import library.Tracer;

public class AStart {
	private static final int DIRECTION = 4;
	private static final int MAX_DEPTH = 60;// generally speaking, depth is
											// about 25
	private TreeSet<Node> openTab;// priority queue
	private List<Node> closedTab;

	public AStart() {
		closedTab = new ArrayList<Node>();
		openTab = new TreeSet<Node>(new Node(""));
	}

	public Node find(Node node) {
		openTab.add(node);

		Node curr = null;
		Node child, tmp;
		Iterator<Node> it;
		while (openTab.size() > 0) {
			curr = openTab.first();
			openTab.remove(curr);

			if (!contains(closedTab, curr))
				closedTab.add(curr);

			if (Tracer.isPrinting("scaffolding1") || Tracer.isPrinting("size")) // scaffolding
			{
				Tracer.splitLine("**closed**size:" + closedTab.size());
				Tracer.splitLine("**openTab**size:" + openTab.size());
				curr.disp();
			}

			if (Tracer.isPrinting("scaffolding1"))// scaffolding
			{
				Tracer.splitLine("pop from openTab, add to closedTab");
				curr.disp();
			}

			if (curr.heuristic == 0)
				break;
			if (curr.currentCost > MAX_DEPTH)
				continue;

			for (int i = 0; i < DIRECTION; i++) {
				child = getChildBoard(curr, i);

				if (child == null || contains(closedTab, child))
					continue;

				if (Tracer.isPrinting("scaffolding1"))// scaffolding
				{
					Tracer.splitLine("swap to " + i);
					child.disp();
				}

				for (it = openTab.iterator(); it.hasNext();) {
					tmp = it.next();
					if (tmp.isBoardEquals(child)) {
						if (Tracer.isPrinting("scaffolding1"))// scaffolding
						{
							Tracer.splitLine("scaffolding begin");
							Tracer.splitLine("this element equals to childNode");
							tmp.disp();
							Tracer.splitLine("scaffolding begin");
						}

						if (child.heuristic < tmp.heuristic) {
							openTab.remove(tmp);
							child.pred = curr;
							if (!openTab.add(child))
								System.out.println("add fail1");
						}
						child = null;
						break;
					} else if (Tracer.isPrinting("scaffolding")) {
						Tracer.splitLine("tmp is not equal to child : ");
						tmp.disp();
					}
				}
				if (child != null) {
					child.pred = curr;
					if (!openTab.add(child))
						System.out.println("add fail2");
				}
				/*
				 * 1, why openTab contains the node swapped to right ?
				 * openTab.contains(child) is using the implements of
				 * Comparable<Node> to compare
				 */
				// if (openTab.contains(child))
				// {
				// while (it.hasNext())
				// {
				// tmp = it.next();
				// if (child.equals(tmp)
				// && (child.heuristic < tmp.heuristic))
				// {
				// openTab.remove(tmp);
				// child.pred = curr;
				// openTab.add(child);
				// }
				// }
				// }
				// else
				// {
				// child.pred = curr;
				// openTab.add(child);
				// }
			}
		}
		return curr;
	}

	private boolean contains(List<Node> tab, Node child) {
		for (Iterator<Node> it = tab.iterator(); it.hasNext();)
			if (child.isBoardEquals(it.next()))
				return true;
		return false;
	}

	private Node getChildBoard(Node node, int i) {
		Node child = new Node(node);
		if (child.swapTo(i))
			return child;
		return null;
	}
}
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
